greedy algorithm

In what order do you make your selections?

What criteria are appropriate?

Regarding the order

Cases given in question

Minimizing the result of repeated operations, etc.

In the case of matroids, etc., it is obvious because the value you want to increase is from the largest value you want to increase.

Sort by End of Interval" is non-trivial for interval scheduling

How should we think in these cases?

I have a few ideas.

From the largest value you want to maximize

It's a case where the sum of the gains of each option is maximized, and there's a monotonicity in the addition.

In order of strictest to least restrictive

From those with the widest sphere of influence

What you decide later does not affect the optimal solution of your earlier choice.

Sphere of Influence From Outside to Inside Inclusion

In decreasing order of decreasing options

Choose the one that leaves you with the most options.

The set of choices is inclusive and the outermost one is chosen

From the edge of a number line or graph

It's easy to think of it this way because it's easy to see, but being on the edge leads to "less choice reduction," "fewer options," etc.

Greed Law on Matroids

Repeat "Add to the set of elements already selected in order of increasing weight, if it is an element of F even if it is added to the set of elements already selected".

The problem of constructing a minimum global tree by selecting edges so as not to create a closed path.

Repeat "choose if it doesn't make a closed path with an already chosen edge" in order of decreasing side length.

Greedy Law on Matroids Applied to Graphical Matroids

The problem of selecting as many sections as possible so that there are no common parts.

Repeat "If there is nothing in common with the already selected one, select it" in the order of the end of the interval.

Segments with an interval beginning before the chosen "end of the interval" cannot be chosen in the future

That is, the one that leaves the most options to choose the one that ends the interval the fastest.

Perform one of two operations on the number 1. We want the minimum value of the result of N operations.

Both of the two operations have the property "if the number before the operation is small, the result is also small".

Just choose the one with the smaller result for each operation.

monotonicity

Repeat "choose the one with the smaller result of the operation" in the order of time axis.

Coin Issues

I want to pay a certain amount in coins and minimize the number of coins

The amount of the coin is a multiple of the coin in front of it, a property that

Pay as much as you can in big coins.

Repeat "pay as much as you can" in order of the size of the coins

If coin A is a multiple of coin B, the only way to pay the shortfall in amount due to a reduction of one coin A by B is to use two or more Bs, which always increases the number of coins

If it is not a multiple, for example, 5,4,1 to pay 8, there is a pattern that 5 is reduced by 1, 1 is also reduced by 3, and 4 can be paid with 2 cards, -2 cards, and so on

The coin amounts are multiples of each other, so there is zero "too much" and you don't have to worry about the smaller number of coins

Cases like 15,5,3,1 are the same in 9.

Take one character from the beginning or end of string S and add it to T. I want T to be the smallest in dictionary order.

The lexical order criterion has the property that if the first letter is smaller, it is smaller in lexical order, regardless of what comes after it.

Prepare S' with S inverted.

Repeat "Select the smallest of S and S' in lexicographic order and take the first letter" in chronological order.

There are N points on a number line. We want to select some of them so that all the points are included in the "range within distance R from the selected point". Minimize the number of points to be chosen.

Repeat the process of "choosing the rightmost point on the number line that can cover the points not covered by the points already chosen" from left to right.

The problem of finding the shortest path

Initialize the visited vertex with a single starting point

Repeat "Select vertices that have not been visited and can be reached by a single edge from the visited vertices in order of shortest distance from the starting vertex.

Assuming that the distance between the sides is positive

Since the distance of the edge is positive, "V", which is the shortest distance from the starting point among the vertices that are unvisited and reachable by one edge from the visited vertex, has no shortest path through the other unreachable vertices, so

Given two number sequences A and B, pressing the i-th button increments A0 to Ai. We want Ai to be a multiple of Bi for all i. Minimize the number of button presses.

Repeat "press the minimum number of times that Ai and Bi satisfy the condition" in order of increasing i

Inclusion of the sphere of influence, the small one does not affect the large one because the large one with i encompasses the small one

Knapsack-like problem

There are several kinds of goods, given their value and number of pieces, there is a knapsack that holds N pieces of goods, maximize the value of the goods in the knapsack.

Unlike the so-called knapsack problem, it is not "the weight of one undividable item" but "the number of items", so the fact that it can be divided is important.

Repeat "choose as many as you can" in order of value.

Given two vertex sets A, B and the rank of the vertices. Determine if there is a bipartite graph that satisfies the conditions.

Repeat "select and connect the vertex with the highest remaining degree from B" in the appropriate order of A

Actions that do not reduce options the most

A person is holding a piece of luggage, I want to exchange the luggage so that it is held by the original owner. The maximum weight a person can hold differs, and if a person holds a heavy item, it cannot be exchanged afterwards.

Repeat "exchange the luggage for the original owner" in order of weight.

You can always "trade for the original owner."

It might put the recipient out of action, but it doesn't matter because he already has the original package.

What the sender receives is always "lighter than what he had."

Any other order could cause "what comes back is too heavy".

Sort by difference between two choices

Ai/Bi and K A's are chosen for the gain of choice A/B, respectively, and I want to maximize the gain.

Repeat "Select K A's" in the order of Ai-Bi.

Ai+Bi with "choose A", -Ai without, want to make the sum positive with the smallest choice

Repeat "Choose A" until the sum is positive in the order of the greater of 2*Ai+Bi.

Sort the given columns in ascending order

Bring the smallest value to the top, the rest will ignore that value [Same shape issue, one size smaller

Repeat "bring to top" in order of decreasing value

Minimizing the difference between pairs of numbers

I have an even number of numbers, I want to pair them 2 by 2 and minimize the difference.

Repeat "pair with the next number" in order of decreasing value

Pairing the smallest number with any number other than the next will always result in a loss

Removing the pair would result in [Same shape issue, one size smaller

Given a sequence S,T of 0/1, for S you can either shift one 1 to the left or set two 1s in a row to 0. Match T with the least number of moves.

Repeat "If there is an unresolved 1 to the left of yourself in T, shift it, if not, delete it" in order from the front of S

Given a number of intervals, given a point, all the intervals including that point will be removed. I want to remove all intervals with the minimum number of points

Repeat "Select the section immediately before the end" in the order of the earliest end of the section.

This is the option that has the greatest impact on the other sections of the method of removing the "section with the earliest termination"

Given a positive number sequence H,S, where subscript i is chosen Ki th and we want to minimize the maximum of H+SK, construct K

Not in the order of H or S.

Introduce an upper bound X on the maximum value and make it a decision problem to see if it can be realized.

Repeat "selection" in decreasing order of (X-H)/S

Implication: select in order of decreasing number of options not exceeding X

I have a positive sequence Ai,Bi, choose K subscripts, and I want to maximize the ratio of the sums of each of AB

If the problem is to determine whether the ratio is greater than or equal to X, the transformation of the equation leads to a simple sum of (Bi-XAi), which can be maximized by the greedy method of choosing from the larger values.

Repeat "Select" in order of increasing (Bi-XAi)

---

Links to many issues

POJ3253

Ant book p.49

It's a little complicated.

The justification for the greed law is narrowed down to two options in a validating manner.

I solved it with a digit DP, but greed can do it too.

Problems for which the greedy method can lead to an optimal solution and those for which it cannot

Coins that are and are not optimal for the "spend as much as you can from a large amount of coins" coin problem.

1,4,5 no.

Fundamentals of Discrete Optimization Part 5: Matroids and Global Trees of Graphs

Theory and Algorithms for Discrete Convex Analysis

---